package com.dyz.LeetCodeforSwordFingerOffer;

import java.util.LinkedList;
import java.util.Queue;

public class MovingCount13 {
    public static void main(String[] args) {
        int a =  new MovingCount13().movingCount(1,2,1);
        System.out.println(a);
    }
    //动态规划
    public int movingCount(int m, int n, int k) {
        if(m<=0||n<=0||k<0){return 0;}
        //创建回溯访问数组
        boolean[][] isVisited = new boolean[m][n];


        return countDFS(0,0,isVisited,0,k);
    }

    private static int countDFS(int m, int n, boolean[][] isVisited, int count, int k){
        if(m<0||m>=isVisited.length||n<0||n>=isVisited[0].length||isVisited[m][n]||cul(m,n)>k){
            return 0;
        }


        if(cul(m,n)<=k){
            isVisited[m][n] = true;
            //选择,四个方向递归
            count = 1+ countDFS(m+1, n, isVisited, count, k)+
                    countDFS(m-1, n,isVisited, count, k)+
                    countDFS(m, n+1, isVisited, count, k)+
                    countDFS(m, n-1, isVisited, count, k);
        }


        return count;
    }


    //计算位数之和
    private static int cul(int m, int n){
        int res = 0;
        while (m!=0){
            res+=m%10;
            m=m/10;
        }
        while (n!=0){
            res+=n%10;
            n=n/10;
        }
        return res;
    }


    //广度优先 使用队列
    public int movingCount1(int thread, int rows, int cols){
        if(rows < 0 || cols < 0 ) {return -1;}
        int sum = 0;
        boolean[][] vis = new boolean[rows][cols];
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0,0});
        vis[0][0] = true;
        while (!queue.isEmpty()){
            int [] point = queue.poll();//pop 头节点
            int x = point[0];
            int y = point[1];

            //当已经确认机器人可以进入该坐标之后，才需要从这坐标向四个方向扩散
            if(cul(x, y)<=thread){
                sum++; //机器人可以进入该坐标，故计数加一，并从该坐标往四个方向扩散

                //四个方向（x+1, y）(x-1, y)(x, y+1)(x,y-1)
                //右
                if(x+1>=0 && x+1<rows && y>=0 && y<cols && !vis[(x+1)][y]){
                    queue.add(new int[]{x+1, y});
                    vis[(x+1)][y]=true;
                }
                //左
                if((x-1)>=0 && (x-1)<rows && y>=0 && y<cols && !vis[(x-1)][y]){
                    queue.add(new int[]{(x-1), y});
                    vis[(x-1)][y]=true;
                }

                //上
                if(x>=0 && x<rows && (y-1)>=0 && (y-1)<cols && !vis[x][(y-1)]){
                    queue.add(new int[]{x, (y-1)});
                    vis[x][(y-1)]=true;
                }

                //下
                if(x>=0 && x<rows && (y+1)>=0 && (y+1)<cols && !vis[x][(y+1)]){
                    queue.add(new int[]{x, (y+1)});
                    vis[x][(y+1)]=true;
                }
            }
        }
        return  sum;

    }
}
